
'''
22. 括号生成
'''
from typing import List


class Solution:
    '''回溯'''
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        left = n
        right = n
        tmp = ''
        res = []
        self.rollBack(left, right, tmp, res)
        return res

    '''递归回溯'''
    def rollBack(self, left, right, tmp, res: List[str]):
        # 叶子节点
        if left == 0 and right == 0:
            res.append(tmp)

        # 剪枝
        if left > right:
            return

        # 左节点
        if left > 0:
            self.rollBack(left - 1, right, tmp + "(", res)
        # 右节点
        if right > 0:
            self.rollBack(left, right - 1, tmp + ")", res)


if __name__ == '__main__':
    sl = Solution()
    print(sl.generateParenthesis(2))